COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	∂TO mitchell@rutgers (CC tgd)  11:45 20-Jan
C00011 00003	∂TO %rutgers mitchell, shooley 19:28 26-Jan
C00013 00004	∂29-Jan-82  0827	SCHOOLEY at RUTGERS 	analogy papers
C00018 00005	∂06-Feb-82  1106	SCHOOLEY at RUTGERS 	Re: Short answers  
C00021 00006	∂TO schooley@rutgers 17:46 13-Feb-82
C00025 00007	∂TO schooley@rutgers 20:39 13-Feb-82
C00042 00008	∂TO schoolery@rutgers 16:00 3-May
C00044 ENDMK
C⊗;
∂TO mitchell@rutgers (CC tgd)  11:45 20-Jan
Uses of an Analogizing Program
Dr Mitchell,
	I'm just starting serious thesis work, and am looking for advice,
comments and an application domain.
The underlying research question is how to use analogy to enter new data
into an existing KB.

	My current quest is for specific examples of when someone took
an expert system, which worked on one task, and modified it to perform a
slightly different, but still closely related, task.
Tom Dietterich mentioned that you had just this experience, when you
twiddled the mass spec Dendral/MetaDendral system(s) to interpret NMR graphs.

	How well documented was this conversion?   Did you ever write up
the experiences and exasperations encountered during this ordeal?
In particular, where there many times you recall thinking that,
if only you had some analogizing mechanism, you could have saved a vast
amount of work.  

Two possible examples (of times when an analogy program would have been useful):
1. I imagine there were many times that the code used for the mass spec task 
would almost work for the new NMR application, but not quite.
Here you would have to generate a large amount of new code,
which was extremely similar to the original code --
both bodies of code performed, conceptually, the same process.
A sophisticated analogy using program could, perhaps, have made this alteration
automatically -- using its knowledge of the similarities and differences of
the two tasks, together with principles of programming.  (Yes, that would
be a very difficult task, even disregarding the analogy finding/using mechanism...
requiring a non-trivial "automatic programming" module.  The purpose of this
example was to refer to possible uses of analogies in this re-design process,
rather than this particular case.)

2. Another example involves the rules you gave this new Dendral-ish
system: when the rules used for one class of chemicals were essentially
identical to those for another class.
To illustrate, imagine you had just enterred the dozen rules specific to hydrates.
Now comes the time to enter the corresponding rules to be used for
ammoniates.  (To a first approximation,) these new rules should be deducable
from that first set -- making only the changes needed to distinguish
amine compounds from hydrozyl compounds.  
That is, each of these new rules should be analogous to a rule for hydrates.
However, you would have to tediously enter these rules, rather than simply
stating the obvious analogy (linking hydrates to ammoniates, using the known
hydroxyl to amine compound transformation), and letting the analogizing program
do the "busy" work necessary to generate the actual ammoniate rules.
-----

	I realize that the Dendral system is a poor domain for such an analogizing
program, basically due to its rather non-declarative KB,
greatly complicating the chore of reading and alterring its data.
Still, any insights you could offer
(on either this particular question, or on the overall task of analogizing) 
would be much appreciated.

Thanks,
	Russ

∂21-Jan-82  0813	mitchell at RUTGERS (Tom) 	Re: Uses of an Analogizing Program    
To: RDG at SU-AI
cc: Schooley at RUTGERS

Russ,
	That's kind of dim, dark past, but you are absolutely correct in
guessing that it was a frustratingly tedious task to redesign Meta-DENDRAL
to infer NMR rules.  One thing I remember strongly is that the relatively
small change in representation of the rules required small changes in a
million different places spread through the code.  These changes were almost
always the same conceptual change, but took forever to track down and make 
and debug.  A system that knew the difference between the representation of
the rule, the conceptual task that a piece of code was performing on the
rule, and the way the the representation affected the implementation of that
procedure might have been a real win.

	You are probably right that DENDRAL (as currently written) is not 
the place to look for a good domain.  How about studying
analogy in the area of user interfaces?  People who write real programs
spend a lot of time on user interfaces, and its not much fun.  For example,
think of when new utility routines appear on the DEC20 -- they generally 
have flaky interfaces compared to the more mature utilities, and one always
thinks - why don't they give it a good interface, sort of like this other
command has, but with these differences.  There's one practical domain
for analogy, that you might speak with Mike Genesereth about.

	It turns out that at Rutgers we have a research project whose main
focus is studying problem solving by analogy in the domain of digital 
circuit design.  The task we're addressing is: given a working circuit and 
its functional specifications, redesign the circuit to meet a required 
change in its function.  Right now we have a cluster of working papers, as 
well as a very sketchy paper in the last IJCAI.  We're currently working on
a prototype system.  One of the Ph.D. students working on this project, 
Pat Schooley, has written a working paper surveying work on analogy, and 
going through the design of a particular system.  She's currently 
preparing her thesis proposal in the general area of using analogy in
circuit redesign.  So you two might like to get in touch 
(Shooley@Rutgers). I'll ask her to send you her paper.

	Good luck with your thesis work - definitely keep me informed
of your progress - and I'll put you on the mailing list for our circuit
redesign project.

Cheers,
Tom
-------

∂TO %rutgers mitchell, shooley 19:28 26-Jan
∂TO %rutgers schooley 12:15 27-Jan
	(CC TGD)
Analogy-related things
Tom, Ms Schooley -
	Thanks for your quick response, and for adding me to your mailing
list. Also, please do send those papers.  My thesis proposal has grown
beyond a managable size, and is currently in need of drastic reconfiguration.
I'd still be pleased to send the current version over the net,
if you'd like to read it and add comments.
(Does Rutger's have a Dover-style printer?  If not I can SCRIBE the file
into a simpler, (but not as pretty) file.)

I have also generated reams of random thoughts on analogy.
While reading some of the psych/phil/AI literature on analogy,
I attempted to formulate a "naive analogy" theory,
a la Hayes' naive physics, or Tversky's naive statistics.
Using a small set of "intuitve" (read loosely defined) axes I've
begun distinquishing a few of the different SenseS of analogies,
I'm quite interested in comparing this with Ms SHooley's survey.
Anyway, this too I can send.
¬
Please keep me informed of your progress.

Danke,
	Russ
∂29-Jan-82  0827	SCHOOLEY at RUTGERS 	analogy papers

   I do not currently have a copy of the survey paper on-line. I can send you
a copy through the mail if you can give me an address for doing so. The 
paper is a survey of AI systems that have attempted to use analogy in problem
solving  environments.
   The other paper I have done was completed for an independent study project
under Saul Amarel. It describes a geometry problem solving system which uses
analogy when presented with a new problem which is similar to a previously
solved problem. (Note: this system was never actually implemented as a 
computer program.) I would be happy to send a copy of this paper also.
   I would be quite interested to see what you have so far in terms of your
thesis proposal. It would also be quite helpful to me to exchange references
to analogy papers or systems that you have come across in your research.
I would of course be happy to share any sources  which I have that 
you may not have seen as yet.
   My thesis proposal on the use of analogy in digital circuit redesign
is still in a very rudimentary stage at this time. I would be quite 
interested in getting your commments on it as soon as I can get it into 
reasonable shape for you to read.
   Please do keep in touch and let me  know if there is anything I can do 
to help you out.
  Pat Schooley

-------

∂TO schooley@rutgers 12:49 2-Feb
Short answers
Pat:
	Thanks for your quick reply.  Yes, I would definitely like to see your 
AI survey.  I too have been scanning various areas of the literature...
disappointing, isn't it.
Anyway, my best snail mail address is
	Russ Greiner
	Margaret Jacks Hall
	Computer Science Department
	Stanford University
	Stanford, CA  94305-2085
(Given the precision of the 9 digit zip code, the 2nd, 3rd and 4th lines above
may be extraneous.  But they can't hurt...)

Please send your other paper as well.  I'm especially interesting in seeing how
your approach differs from Kling's Zorba, and hearing why it will work better
than Gelernter's (ancient) geometric theorem prover.

As to my miscellaneous thoughts, papers, musings:
I'm just finishing up that "naive analogy" digression; and will mail it on
completion.  The other document is my overgrown proto-proposal.
It too is deficient in many respects, and inaccurate in others.
There are, however, large subsets of it with which I'm quite happy.
Given that caveat, I'm quite willing to invite others to read it and
offer comments. Are you game?
(If so,) shall I snail mail a hard copy? (and to where?)
If not, would you prefer I ship over a press file,
(usable only if you have access to a Xerox "Dover" printer) or a less-elegant
version, requiring nothing more than the naked eye to read?  

Looking forward to continuing collaboration and mutual support,
	Russ 

∂06-Feb-82  1106	SCHOOLEY at RUTGERS 	Re: Short answers  

Russ,
     I am sending copies of my papers via "snail" mail -- do let me
know if they don't arrive in a reasonable amount of time. 
     I am more than game to read whatever you have done on your proposal
or anything else for that matter. The available literature on the use of
analogy in a problem solving domain is indeed sparse and disappointing!
I would also appreciate any references you have come across that I may not
have seen --- I will obviously reciprocate in that regard.
     It might be best at this point if you sent your papers to me via the
U.S. mail at
              Pat Schooley
              Department of Computer Science
              Rutgers University
              Hill Center
              Busch Campus
              New Brunswick, New Jersey 08903

      The opportunity to communicate with someone who has done a good deal of
reading and thought in the area of analogy is really a plus for me. There
don't seem to be that many of us around. I guess that means that people 
consider it to be either too trivial or too difficult a problem -- hopefully
neither is the case. At any rate I look forward to hearing more from you in 
the future.
    Pat Schooley
-------

∂TO schooley@rutgers 17:46 13-Feb-82
Mailings
Pat -

First, I look forward to reading your report(s).
(No, the "reasonable amount of time" you gave for their trip has not
yet passed.)
Second, there'll soon be a bunch of readings en route to you.  
They're mostly excerpts from an Analogy (Computer) Bulletin Board.
@BEGIN(Explanation)
Prof Lindley Darden, of the departments of Philosophy & History of Science 
at the University of Maryland,
has spent many years studying the areas of theory formation and analogy.
Her one term visit here, (from Sept to Dec 1980) proved very profitable 
for both parties  -- dispite our rather different backgrounds and perspectives,
we found we really were addressing essentially the same questions.

As many people wanted to continue the dialogue started during her stay,
we formed a distribution list of interested people, and have had many
lengthly (and occassionally significant) slow-motion conversations.
Anyway, I'm mailing a few of the ones I considered more interesting.

After reading them, let me know if you'd like to be added to the list.
(If you'd like to "talk" with Lindley, she can be reached as DARDEN@SUMEX.)

While on the topic of interested people, let me mention a few others:
	Doug Hofstadter, at U of Indiana (the author of "Godel, Escher, Bach")
is now working on a project (cutesily) named "Seek Whence" which is trying to
"do" analogies.
	Colleen Crangle, of the Philosophy dept here at Stanford, is also
looking into analogies.  She can be reached as (at?) CSD.GRANGLE@SCORE.
	Tom Dietterich, Steve Tappel and Mike Genesereth also have (varying
degrees of) interest in this topic.  Their respective net-addresses are
CSD.DIETTERICH@SCORE, STT@SAIL and CSD.GENESERETH@SCORE.

[Everyone but Doug is now on that analogy distribution list.
Of course a great many other local people have, at some point, indicated some
curiousity about this area, but nothing tangible.]
@END(Explanation)

I'm also mailing a copy of my proposal.
(I decided against biasing you by forwarding Lindley's comments on this draft,
and my subsequent responses --
I'll be glad to send them later if you think they might be relevant.)

The other paper is from some random people at Xerox... I had an extra copy.

My next (computer) message will be a partial list of references,
annotated with my comments/evaluations.

Enjoy,
	Russ
∂TO schooley@rutgers 20:39 13-Feb-82
Misc Readings on Analogy/Metaphor (and related things)
I. Metaphor, Analogy [nonAI]

@Book(Black,
Key = "Black",
Author = "Black, Max",
Title = "Models and Metaphors",
Publisher = "Cornell University Press",
Address = "Ithica", Year = 1962)
@Comment<(For some reason) considered one of the classics.
Title not withstanding, only 2 articles on metaphor.
Those (and 3rd, on Whorf) are worth reading... (see Searle, in M&T)
The rest is on the nature of nature, etc.
I was a bit disappointed -- as much of reasoning seemed sloppy, and
based on too many [implicit] assumptions.
Core idea was that it was useful to use models in understanding something;
and that understanding from model, and understanding via analogy, were
similar processes -- both "non decompositional".  See Boyd, in M&T.)>

@Book(Lakoff,
Key = "Lakoff",
Author = "Lakoff, George and Johnson, Mark",
Title = "Metaphors We Live By",
Publisher = "The University of Chicago Press",
Address = "Chicago", Year = 1980)

@Article(Hof81,
Key = "Hofstadter",
Author = "Hofstadter, Douglas",
Title = "Roles and Analogies in Real and Artificial Worlds",
Extra = "In Metamathetical Themas section",
Journal = "Scientific American",
Month = SEP, Year = 1981)
@Comment<Cute, as usual.  Some relevance to real world; basically
gives the first few obvious facts about analogy, and some
nice examples to drive home his points.>

@Book(M&T,
Key = "Ortony",
Editor = "Ortony, Andrew",
Title = "Metaphor and Thought",
Publisher = "Cambridge University Press", Address = "Cambridge", Year = 1979)
@Comment< Excellent book, with many first rate articles.
Initial overview good, as were chapters by Searle, Ortony, Paivio?
	Rumbelhart, (parts of) Boyd
Reddy's chapter was worth reading, but probably irrelevant.>

@Book(Hesse,
Key = "Hesse",
Author = "Hesse, Mary",
Title = "Models and Analogy in Science",
Publisher = "University of Notre Dame Press", Address = ?,
Year = 1966)
@Comment< So-so -- good at presenting one view of analogy (as matching slots)
(That approach seems way too superficial to work, I feel)
Do read the section on Aristotle, and his view.>

@TechReport(Gentner,
Key = "Gentner",
Author = "Gentner, Dedre",
Title = "The Structure of Analogical Models in Science",
Institution = "Bolt, Beranek and Newman Inc.",
Number = 4451,
Month = JUL, Year = 1980)
@Comment< Worth reading.  She takes the view that the structure of a model
is preserved, not the simple attributes.  (Ie N-ary relations are
significant, while unary relations are incidental.)
... at least in a good science analogy (which is explanatory/predictive)
(Sure... this gives one good HEURISTIC for evaluating a proposed analogy.
Note this approach is quite representation dependent -- ie what makes
some fact a Binary relation rather than a unary one?  This is discussed
in one of the BBD messages.)>

@InProceedings(GentnerA,
Key = "Gentner",
Author = "Gentner, Dedre",
Title = "Studies of Metaphor and Complex Analogies",
Booktitle = "Symposium on Metaphor as Process",
Organization = "A.P.A", Address = "Montreal",
Month = SEP, Year = 1980)
@Comment< She here tries to demonstrate that unary/binary distinction,
by conducting a psychological experiment. (Yawn)>

@Article(Interfield,
Key = "Darden",
Author = "Darden, Lindley and Maull, Nancy",
Title = "Interfield Theories",
Journal = "Philosophy of Science",
Volume = 44, Pages = "43-64",
Year = 1977)
@Comment< Lindley has several papers on "Interfield connections" --
where one can reason about one field (eg genetics) using facts
from another field (consider proto-biochemistry).  This is stronger
than a random analogy -- here there is some "real" reason why
the facts should be linked.>

@Article(NewFields,
Key = "Darden",
Author = "Darden, Lindley",
Title = "Discovery and the Emergence of New Fields in Science",
Journal = "Philosophy of Science",
Publisher = "Philosophy of Science of America Publication",
Editors = "P. Asquith and I. Hacking",
Volume = 1, Pages = "149-160",
Year = 1978)
@Comment< see above>

@TechReport(R&N,
Key = "Rumelhart",
Author = "Rumelhart, David E. and Norman, Donald A.",
Title = "Analogical Processes in Learning",
Institution = "University of California, San Diego",
Number = 8005,
Month = SEP, Year = 1980)
@Comment< Not yet read. >

II. Analogy [AI]

@InProceedings(M&M,
Key = "Genesereth",
Author = "Genesereth, Micheal R.", 
Title = "Metaphors and Models",
Booktitle = "1-AAAI",
Organization = SU, Pages = "208-211",
Month = AUG, Year = 1980)
@Comment< Must read.  A different view/use of analogy.
View: as shared partial theory (see my proposal)
Use: to use efficient data structures
This paper is unfortunately, difficult to understand.
(my subtitle: "What is the Meta in Metaphor For?")>

@InProceedings(Carbonella,
Key = "Carbonell",
Author = "Carbonell, Jaime",
Title = "Invariance Hierarchy in Metaphor Interpretation",
Pages = "292-295",
Booktitle = "3-Cognitive Science",
Organization = "University of California, Berkeley",
Month = AUG, Year = 1981)
@Comment< Nice set of heuristics for evaluating/generating a good analogy --
based on reasonable introspection, nothing more.>

@InProceedings(Carbonellb,
Key = "Carbonell",
Author = "Carbonell, Jaime,", 
Title = "A Computational Model of Analogical Problem Solving",
Pages = "147-152",
Booktitle = "7-IJCAI",
Organization = "University of British Columbia",
Month = AUG, Year = 1981)
@Comment< See above.>

@Article(Kling,
Key = "Kling",
Author = "Kling, Robert E.",
Title = "A Paradigm for Reasoning by Analogy",
Journal = "Artificial Intelligence", Year = 1971, Pages = "147-178",
Volume = 2)
@Comment< Zorba program - for transfering proofs from one area (eg Group theory)
to rings.  Basically exploited isomorphisms. (Anything else?)>

@InCollection(Evans,
Key = "Evans",
Author = "Evans, Thomas G.",
Title = "A Program for Solution of Geometric-Analogy Intelligence Test Questions",
Booktitle = "Semantic Information Processing",
Editor = "Marvin Minsky", Year = 1968,
Publisher = "The MIT Press",
Address = "Cambridge")
@Comment< Solved A:B :: C : ? for ? in {1 2 3 4 5} by matching (predefined) features
found transformation which took A to B, and applied that to C.
(Did some constraint relaxing if no match found...)
Use the obvious, straightforward methods.  
(Even in '66 considered trivial and uninterested.)>

@TechReport(Ana,
Key = "McDermott",
Author = "McDermott, John",
Title = "Learning to Use Analogies",
Institution = CMU, Year = 1979)
@Comment< Not read >

@TechReport(RBrown,
Key = "Brown",
Author = "Brown, Richard",
Title = "Use of Analogies to Achieve New Expertise",
Institution = MIT, Month = APR, Year = 1979, Number = "AI-TR-403")
@Comment< Deals with generating programs "by analogy"
Analogizes from one plan to another.
[From Plan => Program => Code]
Poorly written - ie confusing
depends on pre-defined type hierarchy
not implemented, very unconvincing -- whole task is unimpressive ...
defn of analogy very confusing.>

@Article(Winston,
Key = "Winston",
Author = "Winston, Patrick H.",
Title = "Learning and Reasoning by Analogy", Pages = "689-703",
Journal = "Communications of the ACM",
Month = DEC, Year = 1980,
Volume = 23, Number = 12)
@Comment< Superficial analysis, assuming "obvious" facts about the world.
(Why is Macbeth more like Hamlet? ...)>

III. Analogy [CS, not AI]

@Article(M&Ua,
Key = "Moll",
Author = "Moll, Robert and Ulrich, John Wade",
Title = "Program Synthesis by Analogy",
Journal = "SIGART Newsletter", Volume = "12", Number = "8", Month = AUG,
Year = 1977, Pages = "22-28")
@Comment <Took one program, and twiddled it to do different
task.  Seems unextendable.
Authors addressed obvious shortcomings.>

@InProceedings(M&Ub,
Key = "Moll",
Author = "Moll, Robert and Ulrich, John Wade",
Title = "The Synthesis of Programs by Analogy",
Pages = "592-594",
Booktitle = "6-IJCAI", Organization = "Tokyo", Month = AUG, Year = 1979)
@Comment< see above. >

@InProceedings(Harmful,
Key = "Halasz",
Author = "Halasz, Frank and Moran, Thomas P.",
Title = "Analogy Considered Harmful",
Pages = "?",
Booktitle = "Human Factors in Computer Systems",
Organization = "National Bureau of Standards",
Address = "Gaithersburg, Maryland", Month = MAR, Year = 1982)
@Comment< Justifiably criticizes superficial, one-track analogies.
They fail to realize the fault is not with the idea of analogy,
but with the particular simplistic approach they are showing.>

@TechReport(Evolution,
Key = "Dershowitz",
Author = "Dershowitz, Nachum and Manna, Zohar",
Title = "The Evolution of Programs: A System for Automatic Program Modification",
Number = "AIM-294",
Institution = CSDSU,
Month = DEC, Year = 1976)
@Comment< Modifying a program to achieve a different goal.
Must already have the analogy map.  It can use the correspondences to
transform the code. >

@TechReport(Chen/Findler,
Key = "Chen",
Author = "Chen, David T. W. and Findler, Nicholar V.",
Title = "Toward Analogical Reasoning in Problem Solving by Computers",
Number = "115",
Institution = "State University of New York at Buffalo",
Type = "Department of Computer Science",
Month = DEC, Year = 1976)
@Comment< not yet read >

@TechReport(Thibadeau,
Key = "Thibadeau",
Author = "Thibadeau, Robert",
Title = "Reaching (For) an Understanding about Analogy",
Number = "DCS-TM-8",
Institution = "Rutgers",
Type = "Department of Computer Science",
Month = MAY, Year = 1977)
@Comment< not yet read >

@InProceedings(Clement,
Key = "Clement",
Author = "Clement, John",
Title = "Analogy Generation in Scientific Problem Solving",
Pages = "137-140",
Booktitle = "3-Cognitive Science",
Organization = "University of California, Berkeley",
Month = AUG, Year = 1981)
@Comment< not yet read >

IV. Misc additional readings
	Polya's books, of course
	AM (and now Eurisko) talked a bit of using analogy in its work.
	New stuff by Winston (more of CACM, unfortunately)

Stuff on reformulation -- Amarel.

Not read:
	Suppe's "The Structure of Scientific Theories"

	Tversky 1977
	Shepard 1974

	Leatherdale, WH - "The Role of Analogy, Model and Metaphor in Science"
	[North Holland, 1974]

	Lorenz, K.Z., "Analogy as a source of Knowledge" (Nobel Prize Lecture given
	in Stockholm on Dec 12, 1973).  in "Lez Prix Nobel en 1973", Elsevier:
	New York, 1974.
∂TO schoolery@rutgers 16:00 3-May
Analogy this-and-that
Pat -
	First, I asked Lindley to add you and Richard Keller to the ANALOGY
bulletin board.  (which has been silent for several months, for various
reasons.)  Second, I've been working on a "What's in an Analogy"
paper for several months now.  I now have a draft ready, and am searching
for comments.  Would you be interested in reading it?
If so, shall I snail mail it there, or could I transmit a DOCument file over the
net?  (That file is already to go.)
Finally, I have several comments about your papers.  Might they be relevant?
(or have you moved onto some other area?)

	Let me know what sort of lines you are pursuing now,
whenever you feel confortable discussing them.

	Russ